7860. Judging Troubles
The NWERC
organisers have decided that they want to improve the automatic grading of the
submissions for the contest, so they now use two systems: DOMjudge and Kattis.
Each submission is judged by both systems and the grading results are compared
to make sure that the systems agree. However, something went wrong in setting
up the connection between the systems, and now the jury only knows all results
of both systems, but not which result belongs to which submission! You are
therefore asked to help them figure out how many results could have been
consistent.
Input. Consists of:
·
one line with one integer n (1 ≤ n ≤ 105), the number of submissions;
·
n lines, each with a result of the judging by
DOMjudge, in arbitrary order;
·
n lines, each with a result
of the judging by Kattis, in arbitrary order.
Each result is a string of length between 5 and 15 characters
(inclusive) consisting of lowercase letters.
Output. Output
one line with the maximum number of judging results that could have been the
same for both systems.
|
Sample input |
Sample output |
|
5 correct wronganswer correct correct timelimit wronganswer correct timelimit correct timelimit |
4 |
SOLUTION
data
structures
Algorithm
analysis
In the problem one should calculate which
and how many judging results were obtained by the DOMjudge and Kattis systems.
If the result s was obtained by the
DOMjudge system a times, and by the
Kattis system b times, then the
number of identical results s is
equal to min(a, b).
Count in the map map<string, int> cnt the number of results s
returned by the DOMjudge system. Further, for each result s of the Kattis system, decrease the value of cnt[s] by one (if cnt[s] > 0). Count the number of such
reductions – it equals to the maximum number of
results that were the same for both systems.
Example
Count the number of results by the DOMjudge
and Kattis systems in the given sample.
4 results were identical in the systems.
Algorithm realization
Declare
the map cnt, where
cnt[s] stores
the number of results s returned by
the DOMjudge system.
map<string, int> cnt;
Read
the number of submissions n.
scanf("%d\n", &n);
Count the number of results of the DOMjudge system.
for (i = 0; i < n; i++)
{
gets(s);
cnt[s]++;
}
Process the results of the Kattis system.
res = 0;
for (i = 0; i < n; i++)
{
gets(s);
If the result s
occurred in the
DOMjudge (cnt[s] > 0),
then decrease cnt[s] by one and increase the counter of results res, which would be the same
for both systems.
if (cnt[s] > 0)
{
cnt[s]--;
res++;
}
}
Print
the answer.
printf("%d\n", res);
Java realization
import java.util.*;
public class Main
{
static Map<String,
Integer> cnt = new
HashMap<String, Integer>();
public static void main(String[] args)
{
Scanner con = new
Scanner(System.in);
int n = con.nextInt();
for(int i = 1; i <= n; i++)
{
String s = con.next();
if (!cnt.containsKey(s))
cnt.put(s, 1);
else
cnt.put(s, cnt.get(s) + 1);
}
int res = 0;
for(int i = 1; i <= n; i++)
{
String s = con.next();
if (cnt.containsKey(s) && cnt.get(s) > 0)
{
cnt.put(s, cnt.get(s) - 1);
res++;
}
}
System.out.print(res);
con.close();
}
}